package com.algorithm.ch1.cjm.dynamic;

/**
 * 打家劫舍
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是
 * 相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
 * <p>
 * 例如：
 * 输入: [1,2,3,1]
 * 输出: 4
 * 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 * 偷窃到的最高金额 = 1 + 3 = 4 。
 */
public class Rob {

    public static void main(String[] args) {

//        int[] nums = new int[]{6,3,10,8,2,10,3,5,10,5,3};

        long time = System.currentTimeMillis();

        int[] nums = new int[]{1,4,4,5,3};

        System.out.println(new Rob().rob3(nums));

        long time1 = System.currentTimeMillis();
        System.out.println((time1 - time));
    }

    /**
     * 递归法
     * leetcode 耗时9ms
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {

        if(nums == null || nums.length == 0) {
            return 0;
        }

        int r = robR(nums,nums.length - 1);

        return r;
    }

    private int robR(int[] nums, int index){

        if(index == 1) {
            return Math.max(nums[0], nums[1]);
        } else if(index == 0) {
            return nums[0];
        } else if(index < 0) {
            return 0;
        }

        //安装2来分隔
        if(nums[index] >= nums[index - 1]) {
            return nums[index] + robR(nums, index -2);
        }

        if(nums[index - 1] >= nums[index] + nums[index - 2]) {
            return nums[index - 1] + robR(nums, index - 3);
        }

        int max = nums[index -1] + robR(nums, index -3);
        int max1 = nums[index] + nums[index - 2] + robR(nums, index -4);

        return Math.max(max, max1);
    }

    /**
     * 记事本法
     * 动态规划
     * leetcode 耗时6ms
     * @param nums
     * @return
     */
    public int rob1(int[] nums){

        if(nums == null || nums.length ==0) {
            return 0;
        }

        ///记事本法保存结果
        int[] res = new int[nums.length];

        int index = nums.length - 1;
        while (index >= 0){

            res[index] = -1;
            index--;
        }

        return robR1(nums, nums.length - 1, res);
    }

    private int robR1(int[] nums, int index, int[] res){

        if(index == 1){

            res[1] = Math.max(nums[0], nums[1]);
            return res[1];
        } else if(index == 0){

            res[0] = nums[0];
            return res[0];
        } else if(index < 0){
            return 0;
        }

        if(res[index] != -1) {
            return res[index];
        }

        if(nums[index] >= nums[index - 1]){

            res[index] = nums[index] + robR1(nums, index -2, res);

            return res[index];
        }

        if(nums[index - 1] >= nums[index] + nums[index - 2]){
            res[index] = nums[index - 1] + robR1(nums, index - 3, res);

            return res[index];
        }

        int max = nums[index -1] + robR1(nums, index -3, res);
        int max1 = nums[index] + nums[index - 2] + robR1(nums, index -4, res);

        res[index] = Math.max(max, max1);

        return res[index];
    }



    /**
     * 自下而上的动态规划
     * 耗时 5ms
     * @param nums
     * @return
     */
    public int rob2(int[] nums){

        if(nums == null || nums.length ==0) {
            return 0;
        }

        int[] res = new int[nums.length];

        res[0] = nums[0];

        int length = nums.length;

        if(length > 1) {
            res[1] = Math.max(nums[0], nums[1]);
        }

        for (int i = 2; i < length; i++) {

            if(nums[i] >= nums[i-1]){
                res[i] = nums[i];

                if(i > 1) {
                    res[i] += res[i - 2];
                }

            }else if(nums[i - 1] >= nums[i] + nums[i - 2]){

                res[i] = nums[i - 1];

                if(i > 2) {
                    res[i] += res[i -3];
                }

            }else {

                int max = nums[i -1];

                if(i > 2) {
                    max += res[i - 3];
                }

                int max1 = nums[i] + nums[i - 2];
                if(i > 3){
                    max1 += res[i - 4];
                }

                res[i] = Math.max(max, max1);
            }
        }

        return res[length - 1];
    }


    /**
     * leetcode最优解
     *
     * @param nums
     * @return
     */
    public int rob3(int[] nums) {
        if(nums==null||nums.length<1){
            return 0;
        }
        int n=nums.length;
        if(n==1){
            return nums[0];
        }
        if(n==2){
            return Math.max(nums[1],nums[0]);
        }
        int fn=0;
        int fn1=Math.max(nums[1],nums[0]);
        int fn2=nums[0];
        int i=2;
        while(i<n){
            fn=Math.max(fn1,fn2+nums[i]);
            fn2=fn1;
            fn1=fn;
            i++;
        }
        return fn;
    }

}

